A. Field of the Invention
The present invention relates to the field of local area network (LAN) hubs. Specifically, the present invention relates to an distributed memory switching hub that connects heterogeneous LANs.
B. Description of the Related Art
Client/server computing architecture provides for a large number of clients, i.e., desktop computing devices such as PCs, distributed across an enterprise to be connected in a data network in order to share information and resources located at one or more locations within the enterprise. The information and resources are generally located within or maintained by high performance computer systems called servers and may comprise application software, databases, high speed peripherals or large mass storage devices. Client/server computing architecture has traditionally been based on local area network (LAN) technology such as 10 Mb/s Ethernet or, more generally, a 10 Mb/s bus employing the well known carrier sense, multiple access bus with collision detection (CSMA/CD) to transmit data.
Over the past decade, the number of devices, or "end stations" connected to CSMA/CD LANs and the amount of information transferred between such end stations has grown rapidly. The growth has led to congestion affecting the performance of such LANs. Congestion can be overcome to some degree by partitioning a LAN into multiple segments via bridges or routers. While providing access to the entire data network, these devices electrically isolate the separate segments, thereby reducing the congestion and collisions that can occur when multiple end stations attempt to transmit data at the same time onto the same LAN segment. Bridges and routers have additional capabilities which allow them to properly discard frames of data that would otherwise be unnecessarily transmitted across LAN segments to which they are connected, thereby further reducing unnecessary traffic over the interconnected LAN segments. However, the overall transmission speed of the enterprise-wide data network is still limited to the speed of the underlying LAN technology employed. Furthermore, the presence of bridges and routers, while reducing unnecessary traffic, introduce yet another source of congestion due to the processing overhead incurred as frames of data traverse bridges and routers within the internetwork.
The relatively slow transmission speed of a CSMA/CD LAN, the bridge or router processing overhead encountered as information traverses the data network, and the increasing use of imaging, distributed database management, multimedia or other data-intensive software applications all contribute to an increasingly congested data network. CSMA/CD LAN switching is another approach to reducing network congestion between multiple LAN segments. When a client sends information to a server in another LAN segment, the CSMA/CD LAN switch determines the proper segment to which the information is destined and forms a connection between the appropriate segments. While reducing data network congestion, this approach is also limited to the 10 Mb/s transmission speed of a CSMA/CD LAN. Thus, the inability of existing technology to satisfactorily resolve problems encountered due to greater volumes of traffic on the today's data networks has prompted the development and use of higher speed LAN technologies such as 100 Mb/s Fiber Distributed Data Interface (FDDI), Fast Ethernet, also 100 Mb /s, and Asynchronous Transfer Mode (ATM), which allows speeds from 155 Mb/s up to 622 Mb/s.
Relative to CSMA/CD LAN technology, higher speed LAN technologies, for example, FDDI, are expensive to implement at every desktop. Furthermore, migrating every existing end station in a CSMA/CD LAN to a FDDI ring precludes leveraging investments in CSMA/CD LAN technology and equipment such as software, drivers, adapters, hubs and bridges. Additionally, given the present requirements of client/server applications, it is not necessary to provide 100 Mb/s or greater transmission speeds to every end station in the data network. A client, which requires low cost connectivity to the data network, typically communicates with only one server, and needs a quick response to requests sent to the server. On the other hand, a server needs to respond quickly to requests from a potentially large number of clients while at the same time managing information and resources. Thus, servers can benefit greatly from the increased bandwidth achieved by migrating to a high speed LAN environment, such as FDDI, while clients might see only an incremental benefit in their performance. By migrating to a FDDI ring only those end station s, e.g., servers, requiring such transmission speed, a substantial increase in the performance of a data network can be achieved, while at the same time, substantial savings can be realized.
As has been indicated above, FDDI and CSMA/CD LANs are different LAN technologies in at least certain respects. For example, a FDDI ring supports 100 Mb/s transmission speed, while a CSMA/CD bus supports 10 Mb/s transmission speed. Additional differences, such as, but not limited to, the method of accessing and transmitting data on the medium, frame formats, and frame lengths exist. It is not possible for a client operating in a CSMA/CD LAN environment to directly communicate with a server that has been migrated to a FDDI environment. A hub comprising one or more FDDI and CSMA/CD LAN ports may be used so that CSMA/CD LAN-based end stations can communicate with FDDI-based end stations, thereby increasing the performance of the data network without abandoning existing investments in CSMA/CD LAN technology at the desktop.
FIG. 1 provides a diagram of a typical enterprise-wide data network topology including an embodiment of distributed memory switching hub 18 interconnecting FDDI ring 16 to one or more CSMA/CD LAN segments 12. Although FIG. 1 includes a FDDI ring, an embodiment of distributed memory switching hub 18 could interconnect one or more CSMA/CD LAN segments 12 to any high speed network, for example, Fast Ethernet or ATM. Multiple CSMA/CD LAN segments 12 may be coupled to a single 10Base-T hub 17, although FIG. 1 shows only one CSMA/CD LAN segment 12 coupled to a 10Base-T hub 17. 10Base-T hub 17, in turn provides a connection between a CSMA/CD LAN port 11 on distributed memory switching hub 18 and the attached CSMA/CD LAN segments 12 via segment 21, itself a CSMA/CD LAN. Distributed memory switching hub 18 functions as a CSMA/CD LAN switch, as described above. Additionally, distributed memory switching hub 18 has one FDDI port 19 through which it is coupled by fiber optic cable 20 or UTP wiring to FDDI concentrator 15. FDDI concentrator 15 can act as a collapsed FDDI ring ("collapsed backbone") or provide a connection to physical FDDI ring 16. In alternative embodiments, multiple FDDI ports may be utilized. FDDI concentrator 15, in turn, provides a connection to a number of servers 14 that are each configured with an appropriate FDDI adapter and software driver. Distributed memory switching hub 18 provides a connection between FDDI concentrator 15 and its associated servers 14 and 10Base-T hubs 17, their associated CSMA/CD LAN segments 12 and attached clients 10. Thus, distributed memory switching hub 18 allows both FDDI and CSMA/CD LAN technologies to coexist in an enterprise-wide data network, thereby enhancing the performance of the client/server computing paradigm.
A switching hub is a computer system including software optimized to receive and transmit frames of data between LAN segments. Referring to FIG. 2, as an optimized computer system, prior art switching hub 35 is generally comprised of the same components as a general purpose computer system, including a central programmable processor 30, an internal control and data bus 33 and shared common memory 31 controlled by central programmable processor 30. Additionally, prior art switching hub 35 has a plurality of low speed media access controllers (MACs) 34, each having an associated LAN port 36 coupled to, for example, a CSMA/CD bus 38. Recent switching hubs interconnect heterogeneous local area networks operating at different transmission speeds, and thus, may also include one or more high speed MACs 32 each having an associated LAN port 37 coupled to, for example, a FDDI ring 39.
A switching hub architecture based on a central programmable processor and shared common memory has numerous drawbacks. First, when a frame of data is received, LAN port 36 at which it is received needs to gain access to shared common memory 31 to fully store the frame because its associated low speed MAC 34 provides little or no buffering capacity at LAN port 36. If LAN port 36 is not able to gain access to shared common memory 31, for example, because multiple LAN ports are simultaneously attempting to access shared common memory 31, LAN port 36 may enter blocking mode, discarding the frame of data. Thus, high speed memory prevents LAN port 36 from entering blocking mode and discarding a frame. Second, such an architecture does not scale well because memory bandwidth needs to be increased to accommodate any additional LAN ports. Third, when a frame of data is simultaneously multicast or broadcast out all LAN ports, as many copies as there are LAN ports need to be generated and queued for transmission, since each LAN port 36 has an associated transmit queue in shared common memory 31. The overhead and inefficiency of this operation in terms of memory space usage and internal bus 33 traffic is obvious. Fourth, if it is determined that a frame of data already received and stored in shared common memory 31 is to be discarded, for example, due to an address compare mismatch, central programmable processor 30 needs to access shared common memory 31 to flush the frame or mark it as invalid. Finally, in prior art switching hubs, the maximum frame forwarding rate is limited because central programmable processor 30 and shared common memory 31 are both involved in receiving, storing and forwarding each frame of data.
As will be seen, the present invention overcomes the above mentioned drawbacks inherent in a switching hub architecture comprising a central programmable processor 30 and shared common memory 31.
The most recent generation of switching hubs receive and transmit frames of data between heterogeneous LAN segments, e.g., 100 Mb/s FDDI, 16 Mb/s Token Ring, and 10 Mb/s CSMA/CD Bus. Switching hubs that interconnect heterogeneous LANs need to account for, among other things, the different transmission speeds at which such LANs operate. In prior art switching hubs, a circuit comprising shared memory stores frames of data, while another, entirely separate circuit adapts for the different rates at which such frames are transmitted. Each circuit typically contains multiple physical devices. A significant simplification in circuitry and concomitant reduction in cost can be achieved by combining the circuitry for storing frames of data with the circuitry for adapting between dissimilar LANs operating at different transmission speeds. The present invention provides this simplification in circuitry.
Switching hubs that interconnect heterogeneous LANs need to also account for the different data encapsulation or frame formats adhered to by different local area network architecture. The switching hub needs to translate frames of data to the proper frame format used by the destination LAN when forwarding them to that LAN. Such translation may require manipulating a frame of data by removing or deleting particular fields within the frame, inserting fields, and swapping the bit-order sequence of yet other fields. A common method of translating frame formats in prior art switching hubs is to receive and store a complete frame of data in a scratchpad area of shared memory where fields are deleted, inserted, or otherwise manipulated by a central programmable processor. Translating the frame typically involves moving blocks of data representing various fields of the frame around in the scratchpad area of memory to provide space for adding new fields or remove space representing fields that have been deleted. Translating frames in this manner may require asynchronous memory and special circuitry capable of gathering and concatenating the output data stream from non contiguous locations within the scratchpad area of shared memory, if the switching hub is to maintain a constant flow of data. Thus, the process involves complex circuitry and significant processing overhead that negatively impacts the switching hub's throughput (measured in frames per second). As will be described, the present invention does not require a central programmable processor or shared common memory resources to translate frames for transmission between heterogeneous interconnected LANs.
Yet another issue that arises when interconnecting heterogeneous local area networks operating at different transmission speeds is broadcast or multicast storms. Broadcast or multicast storms among homogenous interconnected LANs are well known to those of ordinary skill in the art. The problem can become even more severe when interconnecting heterogeneous LANs operating at different transmission speeds because of the ease with which a LAN operating at a relatively faster transmission speed, e.g., FDDI or ATM, can flood one or more LANs operating at a lower transmission speed, e.g., CSMA/CD bus or token ring, with large numbers of broadcast or multicast frames. Prior art MAC layer devices such as bridges or switching hubs have the ability to filter, i.e., to block, specific broadcast or multicast frames from being forwarded from one LAN to another LAN. The present invention replaces this limited all or nothing approach with a more flexible solution in which multicast and broadcast frames are transmitted at a maximum rate that can be individually tuned for each interconnected low speed local area network. Furthermore, prior art switching hubs utilize software executed by a central programmable processor to perform frame filtering and, as such, compete with other functions performed by the switching hub, causing performance degradation of the entire hub when broadcast or multicast storms occur.
Rather than a fixed central bus architecture, a prior art switching hub could employ a cross point switch architecture. A switching hub employing a cross point switch architecture provides dynamic connections between local area networks based on the destination MAC address of a frame received at a LAN port on the hub. Referring to FIG. 3, cross point switching hub 40 is comprised of a cross point switch 44, a plurality of media access controllers (MACs) 43, each having a LAN port 48 coupled to a local area network 47. Each MAC 43 is further coupled to address filter 41 by way of a request line 42. Address filter 41 learns and maintains a list of MAC addresses and the LAN port 48 over which the end station to which the MAC address belongs is located. It also maintains state information about the current state of each MAC 43 and any dynamic links 45 between it and another MAC 43. Address filter 41 is coupled via switch control lines 46 to cross point switch 44. Dynamic links 45 between MACs 43 are controlled by address filter 41. Address filter 41 "throws a switch", that is, it sends a signal to cross point switch 44 over switch control lines 46, dynamically linking two or more MACs when a frame needs to be forwarded between the MACs.
The basic operation of prior art switching hub 40 is as follows. When a frame of data is received at a LAN port 48, the associated MAC 43 informs address filter 41 of the destination MAC address contained therein via request line 42. Address filter 41 determines from its list of MAC addresses the LAN port number of the LAN port 48 associated with the MAC 43 out which the frame should be transmitted. Address filter 41 sends a signal over switch control lines 46 to cross point switch 44 instructing it to form a dynamic link 45 between source MAC 43 and destination MAC 43. Source MAC 43 then transfers the frame over dynamic link 45 to destination MAC 43. After the frame of data is transferred, Address filter 41 sends another signal to cross point switch 44 to remove dynamic link 45 between source MAC 43 and destination MAC 43. The cross point switch architecture is very fast in terms of frame forwarding rates because of the low latency in establishing a dynamic link and immediate transmission of frames of data between MACs. When a dynamic link is formed between a first LAN port and a second LAN port, other LAN ports are unable to link to either the first or the second LAN port, and thus, may discard frames.
A disadvantage of prior art switching hub 40 arises when a dynamic link is formed between any two MACs 43 that do not provide for any buffering of frames of data. As a result, each local area network to which LAN port 48 of each MAC 43 is coupled needs to operate at the same transmission speed. Thus, prior art switching hub 40 can not interconnect heterogeneous LANs operating at different transmission speeds.
Prior art switching hub 40 shares another disadvantage found in prior art switching hub 35 of FIG. 2. In order to send a broadcast frame, a MAC 43 needs to form a dynamic link 45 between every other MAC 43. If, however, other dynamic links currently exist between other MACs, MAC 43 will either enter blocking mode and discard any frames received until such time as a dynamic link is formed and the broadcast frame transferred, or establish a separate, additional dynamic link for transmission of broadcast or multicast frames. The latter alternative requires circuitry necessary to support multiple dynamic links between any two MACs 43.
A similar problem can occur when a first MAC 43 attempts to transfer a frame of data to a second MAC 43 that already has a dynamic link established with a third MAC 43 and is transferring large amounts of data between itself and third MAC 43. First MAC 43 will wait until the dynamic link between second and third MACs 43 is removed before establishing a dynamic link of its own with second MAC 43 and transferring data. While first MAC 43 waits for dynamic link establishment, it enters blocking mode and discards any frames received.
As will be seen, the present invention further overcomes the above mentioned drawbacks inherent in a hub architecture comprising a cross point switch.